# 基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
# 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
#
#  例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
#  另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
#
#  给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成
# 此基因变化，返回 -1 。
#
#  注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
#
#  示例 1：
# 输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
# 输出：1
#
#  示例 2：
# 输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
# 输出：2
#
#  示例 3：
# 输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
# 输出：3

from collections import deque
from typing import List


class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        """
        bfs，遍历每一层的变化，直到变成了目标的基因序列为止就是最少的变化次数
        """
        bank_set: set[str] = set(bank)
        if endGene not in bank_set:
            return -1

        def replace_char_at_index(string: str, index: int, new_char: str) -> str:
            return string[:index] + new_char + string[index + 1:]

        # print(replace_char_at_index(startGene, 7, 'A'))
        # print('AACCGGTA' == 'AACCGGTA')
        que = deque[(str, int)]([(startGene, 0)])
        # que.append(startGene)
        while que:
            cur, step = que.popleft()
            for i, x in enumerate(cur):  # 对基因序列的每个位置使用 'ACGT' 逐个尝试进行替换
                for g in 'ACGT':
                    if g != x:
                        tmp_next = cur
                        tmp_next = replace_char_at_index(tmp_next, i, g)
                        if tmp_next in bank_set:
                            if tmp_next == endGene:
                                return step + 1
                            bank_set.remove(tmp_next)  # 避免多次访问
                            que.append((tmp_next, step + 1))
        return -1


if __name__ == '__main__':
    start, end, bank = "AACCGGTT", "AACCGGTA", ["AACCGGTA"]
    start, end, bank = "AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
    start, end, bank = "AAAAAAAT", "CCCCCCCC", ["AAAAAAAC", "AAAAAAAA", "CCCCCCCC"]
    print(Solution().minMutation(start, end, bank))
